Theory of Computation
Q241.
Consider the following problem x . Given a Turing machine M over the input alphabet \Sigma, any state q of M. And a word w \in \Sigma *) does the computation of M on w visit the state q ? Which of the following statements about x is correct ?Q242.
Let \Sigma be a finite non-empty alphabet and let 2^{\Sigma^{*}} be the power set of \Sigma^{*} . Which one of the following is TRUE?Q243.
Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then, is \bar{L} also context-free? 3) If L is a regular language, then, is \bar{L} also regular? 4) If L is a recursive language, then, is \bar{L} also recursive?Q244.
Let A \leq _{m}B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?Q245.
Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-freeQ246.
A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?Q247.
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is true?Q248.
Consider the following sets: S1: Set of all recursively enumerable languages over the alphabet {0, 1}. S2: Set of all syntactically valid C programs. S3: Set of all languages over the alphabet {0, 1}. S4: Set of all non-regular languages over the alphabet {0, 1}. Which of the above sets are uncountable?Q250.
Which of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1)\capL(N2) = \phi? II. Given a CFG G = (N,\Sigma ,P,S) and a string x \in\Sigma ^*, does x \in L(G)? III. Given CFGs G1 and G2, is L(G1) = L(G2)? IV. Given a TM M, is L(M) = \phi?